257. Binary Tree Paths

給定一棵 Binary Tree，要求找出所有從根節點到葉子節點的路徑，並以字符串形式返回，每一條路徑以「->」符號分隔節點。
用遞迴做的話一定會在這個函數下額外包一個 dfs 方法做，因為需要有變數儲存「->」這個文字。

class Solution(object):
    def binaryTreePaths(self, root):
        """
        :type root: TreeNode
        :rtype: List[str]
        """
        out_str = ""
        all_out_str = []
        def dfs(out_str, all_out_str, root):
            if not root:
                return

            out_str += str(root.val)

            if not root.left and not root.right:
                all_out_str.append(out_str)
                return

            out_str += "->"
            dfs(out_str, all_out_str, root.left)
            dfs(out_str, all_out_str, root.right)
        dfs(out_str, all_out_str, root)

        return all_out_str

步驟如下：

1. 遞迴遍歷：從根節點開始，沿著樹的每一條分支深入，直到達到葉子節點。
2. 構造路徑：每當經過一個節點，將該節點的值加到當前路徑中。
3. 判斷葉子節點：當一個節點的左右子節點均為空時，代表這是一個葉子節點，將完整路徑存入結果。
4. 回溯：遍歷結束後回溯，繼續遍歷其他路徑。

994. Rotting Oranges

這題蠻有意思的，會有一個m x n的網格，其中每個單元格可以具有三個值之一：
0代表沒有橘子;1代表新鮮的橘子;2代表一個腐敗的橘子，
每經過一分鐘，任何與腐爛橘子相鄰的橘子會腐敗，要計算所有橘子腐敗時間要多久，如果最終無發讓所有橘子腐爛的話返回-1

from collections import deque
class Solution(object):
    def orangesRotting(self, grid):
        """
        :type grid: List[List[int]]
        :rtype: int
        """
        queue = deque()
        fresh_oranges = 0
        rows, cols = len(grid), len(grid[0])  # 使用不同的變數保存行數和列數

        # Step 1: 初始化，把腐爛橘子的座標加入隊列，並統計新鮮橘子的數量
        for y in range(rows):
            for x in range(cols):
                if grid[y][x] == 2:
                    queue.append((x, y))  # 將座標作為元組加入隊列
                elif grid[y][x] == 1:
                    fresh_oranges += 1

        # 如果沒有新鮮橘子，直接返回 0
        if fresh_oranges == 0:
            return 0

        # Step 2: BFS 開始腐蝕橘子
        directions = [(1, 0), (-1, 0), (0, 1), (0, -1)]  # 上下左右四個方向
        step = 0

        while queue:
            step += 1
            for _ in range(len(queue)):
                x, y = queue.popleft()
                for dx, dy in directions:
                    nx, ny = x + dx, y + dy
                    # 使用 cols 和 rows 來檢查範圍，而不是 x 和 y
                    if 0 <= nx < cols and 0 <= ny < rows and grid[ny][nx] == 1:
                        grid[ny][nx] = 2  # 新鮮橘子變腐爛
                        fresh_oranges -= 1
                        queue.append((nx, ny))  # 將新腐爛的橘子座標加入隊列

        # 如果還有新鮮橘子，無法完全腐爛，返回 -1
        return step - 1 if fresh_oranges == 0 else -1

這題想超久，主要是對queue還不太熟悉，再多寫幾題關於bfs的題目！

199. Binary Tree Right Side View

給定一棵二叉樹，想像自己站在二叉樹的右側，返回從右側可以看到的節點值的列表，就是對於每一層，從右邊可以看到的節點應該被加入結果最後返回。
使用bfs解題：

from collections import deque
def rightSideView_bfs(self, root):
    if not root:
        return []
    result = []
    queue = deque([root])
    while queue:
        level_length = len(queue)
        # 遍歷當前層的所有節點
        for i in range(level_length):
            node = queue.popleft()
            # 如果是該層的最後一個節點，將它加入結果
            if i == level_length - 1:
                result.append(node.val)
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)
    return result

使用dfs解題：

    def rightSideView_dfs(self, root):
        """
        :type root: TreeNode
        :rtype: List[int]
        """
        result = []
        def dfs(node, level):
            if not node:
                return
            if level == len(result):
                result.append(node.val)
            dfs(node.right, level + 1)
            dfs(node.left, level + 1)
        dfs(root, 0)
        return result

752. Open the Lock

題目：有一個帶有四個轉盤的鎖，每個轉盤有 10 個數字，從 '0' 到 '9'，轉動每一個轉盤使其向前或向後一位數，每次只能轉動一個轉盤。

鎖的初始組合是 "0000"，給定一個目標組合 target，用最少的步驟將鎖的組合從 "0000" 轉到目標組合，但有一些「死亡組合」deadends，途中不能經過這些組合。
最終要返回將 "0000" 轉到 target 的最小步數，如果無法達到目標，則返回 -1。

這題我完全沒有頭緒...只能先抄作業了

筆記

思路：
這是一個典型的"最短路徑問題"，並且可以將每一個鎖的組合視作一個狀態，由於需要找出最少步數，因此我們可以使用"廣度優先搜索（BFS）"，逐層展開最早找到的解即是最短的解。

步驟：
初始化：將初始組合 "0000" 作為起點加入隊列，同時我們使用一個集合來記錄死亡組合（deadends），以便在搜索過程中避開它們。
廣度優先搜索：
每次從隊列中取出當前狀態，將它與 target 進行比較。如果達到目標，則返回當前步數。
對當前鎖的每一位數，嘗試向上或向下轉動，並生成一個新的組合。如果這個組合不在 deadends 中，且還沒被訪問過，將它加入隊列。
結束條件：如果在 BFS 過程中找到 target，則返回當前步數。如果隊列變空，則返回-1，表示無法達到 target。

from collections import deque

class Solution(object):
    def openLock(self, deadends, target):
        """
        :type deadends: List[str]
        :type target: str
        :rtype: int
        """
        # 將deadends轉為集合，方便快速查找
        dead_set = set(deadends)
        # 如果初始狀態就在deadends中，直接返回-1
        if "0000" in dead_set:
            return -1

        # 初始化BFS的隊列和已訪問集合
        queue = deque([("0000", 0)])  # 初始狀態是"0000"，步數為0
        visited = set("0000")  # 記錄已訪問過的組合，避免重複訪問

        while queue:
            current, steps = queue.popleft()

            # 如果當前組合等於目標組合，返回步數
            if current == target:
                return steps

            # 嘗試對鎖的四個轉盤進行操作
            for i in range(4):
                # 對第 i 個轉盤，向上轉和向下轉
                for direction in [-1, 1]:
                    # 取出第i位的數字，將其轉為新的數字
                    new_digit = (int(current[i]) + direction) % 10
                    # 生成新的組合
                    new_combination = current[:i] + str(new_digit) + current[i + 1:]

                    # 如果新組合不在deadends且沒被訪問過，加入隊列
                    if new_combination not in dead_set and new_combination not in visited:
                        queue.append((new_combination, steps + 1))
                        visited.add(new_combination)

        # 如果無法達到目標，返回-1
        return -1